package com.gitee.feizns.explore.data_structure.test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/3/10
 */
public class Rob {

    public static void main(String[] args) {
        System.out.println(rob(new int[]{ 1,2,1,1 }));
    }

    public static int rob(int[] num) {
        if ( num.length == 1 )
            return num[0];
        return Math.max(rob(num, 0, num.length - 2), rob(num, 1, num.length - 1));
    }

    static Map<String, Integer> CACHE = new HashMap<>();

    private static int rob(int[] num, int index, int end) {
        Integer s = CACHE.get(index + ":" + end);
        if ( s != null )
            return s;
        if ( index == end )
            return num[index];
        int ret = index < end ? Math.max(num[index] + rob(num, index + 2, end), num[index + 1] + rob(num, index + 3, end)) : 0;
        CACHE.put(index + ":" + end, ret);
        return ret;
    }

}
